package org.mianshi.eleme;


/**
 * https://leetcode.cn/problems/3u1WK4/description/
 */

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

 class Solution {

    //遍历
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode dummyHead1 = new ListNode(0);
        dummyHead1.next = headA;

        while (dummyHead1.next!=null){
            ListNode cur1 = dummyHead1.next;
            ListNode dummyHead2 = new ListNode(0);
            dummyHead2.next = headB;
            ListNode cur2;
            while (dummyHead2.next!=null){
                cur2 = dummyHead2.next;
                if (cur1==cur2){
                    return cur1;
                }else {
                    dummyHead2 = dummyHead2.next;
                }
            }
            dummyHead1 = dummyHead1.next;
        }
        return null;
    }
}


class Solution1 {

    //遍历
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA; // 返回相交节点或 null
    }
}



public class 两个链表是否相交 {
    //                                  重合点
    //4 -> 1 -> 8 -> 4 -> 55 -> 0 -> 1 -> 8 -> 4 -> 5
    //5 -> 0 -> 1 -> 8 -> 4 -> 54 -> 1 -> 8 -> 4 -> 5
    public static void main(String[] args) {
        // 创建相交部分
        ListNode intersect = new ListNode(8);
        intersect.next = new ListNode(4);
        intersect.next.next = new ListNode(5);

        // 创建链表 A：4 -> 1 -> 8 -> 4 -> 5
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = intersect;

        // 创建链表 B：5 -> 0 -> 1 -> 8 -> 4 -> 5
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(0);
        headB.next.next = new ListNode(1);
        headB.next.next.next = intersect;

        ListNode intersectionNode = Solution1.getIntersectionNode(headA, headB);
        System.out.println(intersectionNode.val);
    }
}

